{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Approximating the square root using exhaustive enumeration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "number of guesses = 26439\n",
      "2.643900000001155 is close to square root of 7\n"
     ]
    }
   ],
   "source": [
    "x = 7\n",
    "epsilon = 0.01\n",
    "step = epsilon ** 2\n",
    "num_guesses = 0\n",
    "ans = 0.0\n",
    "while abs(ans ** 2 - x) >= epsilon and ans <= x:\n",
    "    ans += step\n",
    "    num_guesses += 1\n",
    "print('number of guesses =', num_guesses)\n",
    "if abs(ans ** 2 - x) >= epsilon:\n",
    "    print('failed on square root of', x)\n",
    "else:\n",
    "    print(ans, 'is close to square root of', x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using bisection search to approximate square root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "low = 0 high = 7 ans = 3.5\n",
      "low = 0 high = 3.5 ans = 1.75\n",
      "low = 1.75 high = 3.5 ans = 2.625\n",
      "low = 2.625 high = 3.5 ans = 3.0625\n",
      "low = 2.625 high = 3.0625 ans = 2.84375\n",
      "low = 2.625 high = 2.84375 ans = 2.734375\n",
      "low = 2.625 high = 2.734375 ans = 2.6796875\n",
      "low = 2.625 high = 2.6796875 ans = 2.65234375\n",
      "low = 2.625 high = 2.65234375 ans = 2.638671875\n",
      "number of guesses = 9\n",
      "2.6455078125 is close to square root of 7\n"
     ]
    }
   ],
   "source": [
    "epsilon = 0.01\n",
    "num_guesses, low = 0, 0\n",
    "high = max(1, x)\n",
    "ans = (high + low) / 2\n",
    "while abs(ans ** 2 - x) >= epsilon:\n",
    "    print('low =', low, 'high =', high, 'ans =', ans)\n",
    "    num_guesses += 1\n",
    "    if ans ** 2 < x:\n",
    "        low = ans\n",
    "    else:\n",
    "        high = ans\n",
    "    ans = (high + low) / 2\n",
    "print('number of guesses =', num_guesses)\n",
    "print(ans, 'is close to square root of', x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using bisection search to estimate log base 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.80859375 is close to the log base 2 of 7\n"
     ]
    }
   ],
   "source": [
    "x = int(7)\n",
    "epsilon = 0.01\n",
    "# find lower bound on ans\n",
    "lower_bound = 0\n",
    "while 2 ** lower_bound < x:\n",
    "    lower_bound += 1\n",
    "low = lower_bound - 1\n",
    "high = lower_bound + 1\n",
    "# perform bisection search\n",
    "ans = (high + low) / 2\n",
    "while abs(2 ** ans - x) >= epsilon:\n",
    "    if 2 ** ans < x:\n",
    "        low = ans\n",
    "    else:\n",
    "        high = ans\n",
    "    ans = (high + low) / 2\n",
    "print(ans, 'is close to the log base 2 of', x)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
